package g

/*
 * @lc app=leetcode.cn id=24 lang=golang
 *
 * [24] 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
*/

// ListNode Definition for singly-linked list.
type ListNode struct {
	Val  int
	Next *ListNode
}

// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	// 交互前两个原始
	// head    q
	// n1  ->  n2  ->  n3
	q := head.Next
	head.Next = q.Next
	q.Next = head
	head = q
	// -----------
	p := head.Next
	q = p.Next
	// head     p       q
	// n2   ->  n1  ->  n3 ->   n4  ->  n5
	// swap n3/n4,p和q分别指向n3的父节点和n3
	for q != nil && q.Next != nil {
		p.Next = q.Next
		// head     p       q
		// n2   ->  n1      n3 ->   n4  ->  n5
		// n2   ->  n1  --------->  n4  ->  n5
		q.Next = p.Next.Next
		// head     p       q
		// n2   ->  n1      n3 ---------->  n5
		// n2   ->  n1  --------->  n4  ->  n5
		p.Next.Next = q
		// head     p              q
		// n2   ->  n1  ->  n4  -> n3  ->   n5
		p = q
		// head                    p,q
		// n2   ->  n1  ->  n4  -> n3  ->   n5
		q = p.Next
		// head                    p        q
		// n2   ->  n1  ->  n4  -> n3  ->   n5
	}

	return head
}

// @lc code=end
